#include <iostream>
#include <vector>
#define INF INT_MAX / 2
using namespace std;
int main(void) {
    int vnums, arcnums;
    cout << "点数" << "边数" << endl;
    cin >> vnums >> arcnums;
    vector<vector<int>> adj(vnums, vector<int>(vnums, INF));
    vector<vector<int>> edges(arcnums, vector<int>(3, 0));
    // 弧尾 弧头 权值
    cout << "依次输入边" << endl;
    for (int i = 0; i < arcnums; ++i) {
        cout << "第" << i+1 << "条边" << endl;
        cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
    }
    // 把边录入邻接矩阵
    for (auto arc: edges) {
        adj[arc[0]][arc[1]] = arc[2];  // 有向图只写这一个就行
        // adj[arc[1]][arc[0]] = arc[2]; // 无向图还要写这一行
    }
    // 开始求最短路
    vector<bool> visited(vnums, false);
    vector<int> dist(vnums, INF); // 记录当前最短距离
    vector<int> parent(vnums, -1);
    int begin;
    cout << "开始节点索引" << endl;
    cin >> begin;
    dist[begin] = 0;
    for (int t = 1; t < vnums; ++t) {
        int min = -1; // 维护距离最短的那个点索引
        for (int i = 0; i < vnums; ++i) {
            if (!visited[i]) {
                if (min == -1 || dist[i] < dist[min])
                    min = i;
            }
        }
        // 此时找到当前距离最短的点
        visited[min] = true;
        for (int i = 0; i < vnums; ++i) {
            if (!visited[i]) {
                if (dist[min] + adj[min][i] < dist[i]) {
                    dist[i] = dist[min] + adj[min][i];
                    parent[i] = min; // 更新到i节点的来源
                }
            }
        }
    }
    // 输出测试数据结果
    cout << "dist" << endl;
    for (auto d: dist) {
        cout << d << " ";
    }
    cout << endl;
    cout << "parent" << endl;
    for (auto v: parent) {
        cout << v << " ";
    }
    cout << endl;
}
// 测试数据
// 节点数 边数量 接下来的每一条边 开始节点
// 4 5  0 1 5  0 2 3  1 2 1  1 3 4  2 3 2   0
// 5 6  0 1 5  0 2 3  0 4 3  2 1 1  1 3 4  2 3 2  0